﻿#include <iostream>
#include <vector>
#include <ctime>
#include <exception>
#include <string>
#include <algorithm>

#include <allocators>



//容器初始化
void test_vector()
{
	std::vector<int> frist;//默认构造函数，构造一个空的容器，没有元素—— explicit vector(const allocator_type& alloc = allocator_type());
	std::vector<bool> b;
	
	b.push_back(true);
	b.push_back(true);
	b.push_back(true);
	b.push_back(true);
	b.push_back(true);
	
	std::vector<int> second(4, 100);//fill 构造函数 用 n 个元素构造一个容器。每个元素都是 val 的副本。—— vector (size_type n, const value_type& val, const allocator_type& alloc = allocator_type());
	
	std::vector<int> third(second.begin(), second.end());//range 构造函数 使用second [begin， end]范围内的元素顺序，构造一个容器，其中的每个元素都是 emplace —— template <class InputIterator> vector(InputIterator frist, InputIterator last, const allocator_type& alloc = allocator_type());

	std::vector<int> fourth(third);//copy 构造函数 按照third 容器的内容构造一个新的副本容器—— vector ( const vector& x);

	//vector(vector &&x) v; —— move 构造函数 构造一个获取x 元素的容器，该动作是将 x 中的元素全部move 给v ，v 将不具有元素。（这个行为不会产生元素的构造和析构动作）

	std::vector<int> sixth({ 1,2,3,4 });//初始化列表构造函数 将{ } 中元素逐个拷贝到容器 sixth 中。
	for (int & val : sixth) std::cout  << val << ' ';

	std::cout << "\n";


}

void test_opeartor_equal()
{
	/*
		vector & operator= (const vector& x);

		vector& operator= (vector&& x);

		vector& operator= (initializer_list<value_type> il) ;
	*/

	std::vector<int> foo(3, 0);
	std::vector<int> bar(5, 0);
	std::vector<int> v = { 1, 2, 3, 4, 5 };


	bar = foo;//这个不知道诶
	foo = std::vector<int>();//因为是在右边，所以很可能调用的是 vector& operator= (vector&& x);

	std::cout << "Size of foo:" << foo.size() << '\n';
	std::cout << "Size of bar:" << bar.size() << '\n';
	std::cout << "Size of v:" << v.size() << '\n';

}

void test_begin()
{
	std::vector<int> v = { 1, 2,3 ,4 ,5 ,6 ,7 ,8 ,9 };
	for (auto it = v.begin(); it != v.end(); it++) {
		(*it)++;
		std::cout << ' ' << *it;
	}

	std::cout << '\n';

	for (auto it = v.rbegin(); it != v.rend(); it++) {
		(*it)++;
		std::cout << ' ' << *it;
	}

	std::cout << '\n';


	for (auto it = v.cbegin(); it != v.cend(); it++) {
		std::cout << ' ' << *it;
	}

	std::cout << '\n';

	for (auto it = v.crbegin(); it != v.crend(); it++) {
		std::cout << ' ' << *it;
	}

	std::cout << '\n';
}

//返回 vector 中元素的数量  这是 vector 中保存的实际对象的数量，不一定等于其存储容量
void test_size()
{
	std::vector<int> v;
	std::cout << "v size:" << v.size() << '\n';

	for (size_t i = 0; i < 10; i++)
	{	
		v.push_back(i);
	}

	std::cout << "v size:" << v.size() << '\n';

	v.insert(v.end(), 5, 5);

	std::cout << " v size:" << v.size() << '\n';

	v.pop_back();

	std::cout << " v size:"  << v.size() << '\n';
}
// max_size 是vector 容器可容纳元素的最大数量。由已知的系统或库限制。这是容器可以达到的最大潜在大小 
void test_max_size()
{
	std::vector<int> v;
	for (size_t i = 0; i < 100000; i++)
	{
		v.push_back(i);
	}

	std::cout << "v size:" << v.size() << '\n';
	std::cout << "v max_size:" << v.max_size() << '\n';
	std::cout << "v cacpcity:" << v.capacity() << '\n';//当前的容器在不扩充的情况下，能容纳的元素大小

	/*
		v size:100000 #10,0000
		v max_size:1073741823 #10,7374,1823
		v cacpcity:138255 #13,8255
	*/
}

class Foo {
public:
	Foo() {
		std::cout << __FUNCTION__ << '\n';
	}
	~Foo() {
		std::cout << __FUNCTION__ << '\n';
	}
};
//resize 调整大小，使其包含 n 个元素。 如果 n 小于当前容器的size，则 size - n 的元素将被销毁；如果n 大于当前容器的size，则通过在末尾插入 n - size 的元素
void test_resize()
{
	std::vector<Foo> v;
	v.resize(7);//调用了7次Foo 的构造函数

	v.resize(3);//调用了4次Foo 的析构函数
	std::cout << '\n';

	v.resize(7);//调用了4次Foo 的构造函数
	std::cout << '\n';

	Foo t;
	v.resize(10, t);
	std::cout << "v size:" << v.size() << '\n';
}

void test_resize_int()
{
	std::vector<int> v;

	for (size_t i = 1; i < 10; i++) v.push_back(i);

	v.resize(5,1);//如果 n 小于当前容器的size ，则 size - n 的数据被释放，即使指定 val 无效

	v.resize(8, 100);//如果n 大于 当前容器的size ，则在末尾插入更多的元素。如果指定了val，则n - size 范围的元素的值为 val

	v.resize(12);

	std::cout << " v contains:";
	for (size_t i = 0; i < v.size(); i++)
		std::cout << ' ' << v[i];

	std::cout << '\n';
	// v contains: 1 2 3 4 5 100 100 100 0 0 0 0

}

void test_capacity()
{
	std::vector<int> v;
	v.resize(100);

	std::cout << "v size:" << v.size() << '\n';
	std::cout << "v capacity : " << v.capacity() << '\n';

	v.push_back(1);

	std::cout << "v size:" << v.size() << '\n';
	std::cout << "v capacity : " << v.capacity() << '\n';

}

//shrink_to_fit 把它从曾经最大的容量，减少到它现在需要的容量  从 v.capacity --> v.size 有可能导致重新分配

void test_shrink_to_fit()
{
	std::vector<Foo> v;
	v.resize(5);

	Foo f;
	v.push_back(f);

	std::cout  << "v size " << v.size() << '\n';
	std::cout << "v capacity " << v.capacity() << '\n';

	v.shrink_to_fit();//为什么在调试状态下，容器中的对象被析构了，元素大小为6，出现了6次析构函数的调用

	std::cout << "shrink to fit " << '\n';

	std::cout << "v size " << v.size() << '\n';
	std::cout << "v capacity " << v.capacity() << '\n';

}

void test_front()
{
	std::vector<int> v(5,5);

	for (size_t i = 0; i < v.size(); i++) {
		std::cout << v[i] << '\n';
		v.at(i) = i;
		std::cout << v[i] << '\n';
	}

	std::cout << "v front:" << v.front() << '\n';
	std::cout << "v back:" << v.back() << '\n';
}

//data vector 增加了 data 的用法，它返回内置vector 所指的数组内存的一个元素的指针
void test_data()
{
	//std::vector<int> v(5, 5);
	//int *p = v.data();
	int arr[5] = { 1, 2, 3, 4, 5};
	int *p = arr;
	std::cout << p << std::endl;
	for (size_t i = 0; i < 5; ++i)
	{
		std::cout << '\t' << *p << std::endl;
		std::cout << " i: " << *p++ << std::endl;
	}
	/*
		74 78
		7c 

	*/
	std::cout << sizeof(int) << sizeof(p) << std::endl;

	
}

void test_assign()
{
	std::vector<int> frist;
	std::vector<int> second;
	std::vector<int> third;

	frist.assign({ 1, 2, 3,4,5 });
	
	std::vector<int>::iterator it;
	it = frist.begin() + 1;

	second.assign(it, frist.end() - 1);

	third.assign(6, 7);

	std::cout << " frist size:" << frist.size() << std::endl;
	std::cout << "second size:" << second.size() << std::endl;
	std::cout << "third size:" << third.size() << std::endl;
}

//push_back  在 vector 的最后一个元素之后，添加一个新元素。val 的内容被复制（或移动）到新的元素
//这有效地将容器size 增加了一个。如果新的矢量 size 超过了当前vector 的capacity ，则导致重新分配一块更大的空间

void test_push_back()
{
	std::vector<int> v;
	v.resize(10);
	v.push_back(1);
	for (size_t i = v.size(); i < v.capacity() ; i++)
	{
		v.push_back(i);
		std::cout << " " << v.capacity() << " " << v.size() << '\n';
	}
	
	std::cout << " " << v.capacity() << " " << v.size() << '\n';
}

//pop_back 删除vector 中最后一个元素，有效地将容器的size - 1
void test_pop_back()
{
	std::vector<int> v;
	v.assign(5, 5);
	int sum = 0;
	while (!v.empty())
	{
		sum += v.back();
		v.pop_back();
	}

	std::cout << "The element of v add up to " << sum << '\n';
}

//insert 通过在指定位置的元素之前插入新元素来扩展该 vector，通过插入元素的数量来增加容器的大小。当vector的size 超过 capacity时，会发生重新分配存储空间。插入动作的复杂度等于v.size - pos。
void test_insert()
{
	std::vector<int> v(5, 5);
	v.insert(v.begin(), 1);
	v.insert(v.end(), 6, 6);

	std::vector<int> v2(5, 100);
	v.insert(v.begin(), v2.begin(), v2.end());
	
	v.insert(v.begin(), { 1,2,3,4,5 });

	for (auto it = v.begin(); it != v.end(); it++)
		std::cout << *it << ' ';

	std::vector<int> v3(5, 5);
	auto it = v3.begin();//获取到一个vector 的迭代器
	v3.insert(v3.end(), 5, 5);
	auto it2 = v3.begin();//再次获取 迭代器
	//v3.insert(it, 5, 5);//如果使用 it 的迭代器，会发生未知的错误，因为vector 大小已经发生了变化，所以旧的迭代器将无法使用
	std::cout << it._Ptr << "   " << it2._Ptr << std::endl;
}

//erase 从vector 中删除单个元素（position）或一个范围的元素（【first， last】）
//由于 vector 使用一个数组作为底层存储，所以删除 除开头和结尾外的元素，将导致容器的其它数据进行重新定位。与其它种类的序列容器执行相同的操作相比，这通常是低效的操作。

void test_erase()
{
	std::vector<int> v;

	for (size_t i = 0; i < 10; i++)
	{
		v.push_back(i);
	}

	v.erase(v.begin() + 5); //earse the 6th element

	std::cout << v.size() << '\n';

	v.erase(v.begin(), v.begin() + 3);
	
	std::cout << v.size() << '\n';

	for (size_t i = 0; i < v.size(); i++)
	{
		std::cout << v.at(i) << ' ' ;
	}

	std::cout << "\n";

}

void printVector(std::vector<int> &v)
{
	for (size_t i = 0; i < v.size(); i++)
	{
		std::cout << v.at(i) << ' ';
	}

	std::cout << '\n';
}

//通过 x 的内容交换容器的内容，x 是另一个相同类型的vector 对象。大小可能不同
//两个容器数据的 **全部元素** 的转换。
void test_swap()
{
	std::vector<int> frist(3, 100);
	std::vector<int> second(5, 200);
	std::vector<int> third(2, 50);

	frist.swap(second);
	printVector(frist);
	printVector(second);
	/*
	200 200 200 200 200
	100 100 100
	*/

	second.swap(third);

	printVector(third);
	printVector(second);
	/*
	100 100 100
	50 50
	*/
}

//clear 清除容器内的元素，此时size 为0，但是容器的capcacity 不受影响
void test_clear()
{
	std::vector<int> v1(15, 50);
	printVector(v1);

	std::cout << "v1.size：" << v1.size() << '\n';
	std::cout << "v1 capacity:" << v1.capacity() << '\n';

	v1.clear();
	std::cout << "v1.size：" << v1.size() << '\n';
	std::cout << "v1 capacity:" << v1.capacity() << '\n';

	v1.push_back(1);
	v1.push_back(2);

	printVector(v1);
	std::cout << "v1.size：" << v1.size() << '\n';
	std::cout << "v1 capacity:" << v1.capacity() << '\n';
}

/*emplace 是 C11 新增加的成员函数，用于在 vector 容器指定位置之前插入一个新的元素
该函数的语法格式如下：
iterator emplace(const_iterator pos, args...);
其中 pos 为指定插入位置的迭代器，args..表示与新插入元素的构造函数相对应的多个参数；
该函数会返回表示新插入元素位置的迭代器

和 instert 相比，emplace 效率更高
*/

class Bar
{
public:
	//Bar() {}
	Bar(int num, int cnt)
		:num(num) {
		std::cout << "ctor" << std::endl;
	}

	Bar(const Bar& other)
		:num(other.num) {
		std::cout << "调用拷贝构造函数" << std::endl;
	}

	~Bar() {
		std::cout << "dtor" << std::endl;
	}

	//Bar(Bar && other)
	//	:num(other.num) {
	//	std::cout << "调用移动构造函数" << std::endl;
	//}
	//Bar operator=(const Bar& other) {
	//	std::cout << "调用赋值构造函数" << std::endl;
	//	return other;
	//}

	Bar& operator=(const Bar& other) = default;
private:
	int num;
};

/* 
emplace 在插入元素时，是在容器的指定位置直接构造元素。
insert 是先单独生成，再将其赋值（或移动）到容器中
*/
void test_emplace()
{
	std::cout << "insert :" << std::endl;
	std::vector<Bar> v1;
	v1.insert(v1.begin(), Bar(1,1));


	std::cout << "emplace: " << std::endl;
	std::vector<Bar> v2;
	v2.emplace(v2.begin(), 1,1);//1,1 args...

	std::cout << "-----------" << std::endl;
		
}

/*emplace_back 和 push_back的区别 和上面emplace insert 相似。
 push_back 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或移动到容器的尾部。（如果是拷贝的话，时候会自行销毁先前创建的元素）
 而emplace_back 在实现时，是直接在容器的尾部创建这个元素。

 该元素是通过 allocator::construct 来转换 args 来创建的
*/
void test_emplace_back()
{
	std::cout << "emplace_back:" << std::endl;

	std::vector<Bar> v1;
	v1.emplace_back(2,2);

	std::cout << "push_back:" << std::endl;
	std::vector<Bar> v2;
	v2.push_back(Bar(1,2));

	std::cout << "-------------endOf" << std::endl;
}
/*
emplace_back:
ctor
push_back:
ctor
调用拷贝构造函数
dtor
-------------endOf
dtor
dtor
*/

//返回 vector 关联的构造器对象的副本
void test_get_allocator()
{
	std::vector<int> v;
	int *p;
	unsigned int i;

	//allocate an array with space for 5 elements using vector's allocator
	p = v.get_allocator().allocate(5);

	for (i = 0; i < 5; i++) v.get_allocator().construct(&p[i], i);

	std::cout << "The allocator array contains:";
	for (i = 0; i < 5; i++) std::cout << ' ' << p[i];
	std::cout << "\n";

	//destroy and dellcator
	for (i = 0; i < 5; i++) v.get_allocator().destroy(&p);

	v.get_allocator().deallocate(p, 5);
	
}

using std::cout;
using std::string;
using std::array;
using std::endl;
using std::vector;


string get_a_target_string()
{
	long target = 0;
	char buf[10];

	cout << "target (0~" << RAND_MAX << "):";
	std::cin >> target;
	snprintf(buf, 10, "%d", target);

	return string(buf);

}

int compareStrings(const void * a, const void * b)
{
	if (*(string*)a > *(string*)b)
		return 1;
	else if (*(string*)a < *(string*)b)
		return -1;
	else
		return 0;
}

void test_vector_2(long & value)
{
	cout << "\n test_vector() ..." << endl;

vector<string> c;
char buf[10];

clock_t timeStart = clock();
	for (long i = 0; i < value; i++)
	{
		try {
			snprintf(buf, 10, "%d", rand());
			c.push_back(string(buf));
		}
		catch (std::exception &p) {
			cout << "i= " << i << " " << p.what() << endl;
			abort();
		}
	}

	cout << "milli-seconds: " << (clock() - timeStart) << endl;
	cout << "vector.size() = " << c.size() << endl;
	cout << "vector.front() = " << c.front() << endl;
	cout << "vector.back = " << c.back() << endl;
	cout << "vector.data() = " << c.data() << endl;
	cout << "vector.capacity() = " << c.capacity() << endl;

string target = get_a_target_string();
	{
		timeStart = clock();
auto pItem = std::find(c.begin(), c.end(), target);
		cout << "find(), milli-seconds: " << (clock() - timeStart) << endl;//循序查找
		if (pItem != c.end()) {
			cout << "found, " << *pItem << endl;
		}
		else {
			cout << "not found!" << endl;
		}
	}

	{
		timeStart = clock();
		sort(c.begin(), c.end());
		string* pItem = (string*)bsearch(&target, (c.data()), c.size(), sizeof(string), compareStrings);

		cout << "sort() + bsearch() , milli-seconds : " << (clock() - timeStart) << endl;

		if (pItem != NULL)
			cout << "found, " << *pItem << endl;
		else
			cout << "not found!" << endl;

	}

	

}


int main()
{
	//test_vector();
	//test_opeartor_equal();
	//test_begin();
	//test_size();
	//test_max_size();
	//test_resize();
	//test_resize_int();
	//test_capacity();
	//test_shrink_to_fit();
	//test_front();
	//test_data();
	//test_assign();
	//test_push_back();
	//test_pop_back();
	//test_insert();
	//test_erase();
	//test_swap();
	//test_clear();
	//test_emplace();
	//test_emplace_back();
	//test_get_allocator();


	//当 value 很大时会出现下面的异常提示。
	//long value = 500000000;
	/*
	i= 11958657 bad allocation
	C:\Users\admin\source\repos\C++STL\Debug\vector.exe (进程 14980)已退出，返回代码为: 3。
	*/

	long value = 500000;
	test_vector_2(value);

	

	
	return 0;
}


